package org.algorithm.二师兄.链表;


import org.algorithm.common.ListNode;

/*****
 *
 *      周末的题：  周一要看，  没写的， 嘿嘿。。。   你们懂的
 *   参考uri: https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 *
 */
public class K个一组反转链表 {

    public static void main(String[] args) {
        ListNode listNode = ListNode.build(1,2,3,4,5);
        ListNode.print(reverseKGroup(listNode, 2));
    }

    private static ListNode reverseKGroup(ListNode listNode, int k) {
        if (listNode == null || listNode.next == null) return listNode;
        int length = 0;
        ListNode temp = listNode;
        while (temp != null) {
            length++;
            temp = temp.next;
        }

        ListNode res = listNode;
        int start = 0;
        while (start + k <= length) {
            // 区间反转
            res = reverseListNodeBetween(res, start, start + k - 1);
            start += k;
        }
        return res;
    }

    private static ListNode reverseListNodeBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode curr = head;
        for (int i = 0; i < left; i++) {
            pre = pre.next;
            curr = curr.next;
        }

        for (int i = left; i < right; i++) {
            ListNode next = curr.next;
            curr.next = curr.next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }


}
